#pragma once

template <typename T> 
class QueueNode
{
public:
    T data;
    QueueNode* prev;
    QueueNode* next;
};

template <typename T> 
class Queue 
{
public:
    Queue();
    ~Queue();

    bool empty() const
    { 
        return _size == 0;
    }

    int size() const 
    { 
        return _size; 
    }

    void push(const T&x);
    void pop();
    T front();
    T back();
private:
    QueueNode<T>* head;
    QueueNode<T>* tail;
    int _size;
};

template <typename T> 
Queue<T>::Queue()
{
    head = new QueueNode <T>;
    tail = new QueueNode <T>;
    head->prev = NULL;
    head->next = tail;
    tail->prev = head;
    tail->next = NULL;
    _size = 0;
}

template <typename T> 
Queue<T>::~Queue() 
{
    while (_size != 0) 
    {
        QueueNode<T>* t;
        t = head->next;
        head->next = head->next->next;
        head->next->prev = head;
        delete t;
        _size--;
    }
}

template <typename T> 
void Queue<T>::push(const T& x) 
{
    QueueNode<T>* t = new QueueNode<T>;
    t->data = x;
    t->prev = tail->prev;
    t->next = tail;
    tail->prev->next = t;
    tail->prev = t;
    _size++;
}

template <typename T> 
void Queue<T>::pop() 
{
    if (_size) 
    {
        QueueNode<T>* t;
        t = head->next;
        head->next = head->next->next;
        head->next->prev = head;
        delete t;
        _size--;
    }
}

template <typename T> 
T Queue<T>::front() 
{
    return head->next->data;
}

template <typename T> 
T Queue<T>::back() 
{
    return tail->prev->data;
}

